题解：AT_abc140_e [ABC140E] Second Sum
题解
思路：双向链表+组合数学（不过你要用单调栈也没人拦着你）
我们现在先抛开题面，先换个思路。
我们现在求：这个数能做多少个区间的次大值。
我们现在设 分别为左边第一个比这个数大的 id，第二个比这个数大的 id，右边第一个比这个数大的 id，第二个比这个数大的 id。竟然是次大值，所以我们左边和右边能且仅能包含一个比这个数大的。
我们现在求区间数即为：
- 左边取一个比他大的数的个数 右边取不比他大的数的个数。
- 右边取一个比他大的数的个数 左边取不比他大的数的个数。
即为：
(l1 - l2) * (r1 - a[i].id)(r2 - r1) * (a[i].id - l1)
那么如何获得 呢？
如果我能直接从当前这个数找到这四个数是最好的，就是说像这样的一个链表：
要实现这样我们可以存好 id 后排序，从小到大处理，根据链表的删除机制，到某个数时，一定会成为类似上图的样子。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
| #include <bits/stdc++.h>
#define ll long long
using namespace std;
ll n;
struct Node
{
ll x;
ll id;
} a[100005];
ll pre[100005], nxt[100005];
ll ans = 0;
bool cmp(Node a, Node b) {
return a.x < b.x;
}
void del(ll id)
{
nxt[pre[id]] = nxt[id];
pre[nxt[id]] = pre[id];
return ;
}
int main()
{
cin >> n;
for (ll i = 1; i <= n; i++)
{
cin >> a[i].x;
a[i].id = i;
pre[i] = i - 1;
nxt[i] = i + 1;
}
nxt[0] = 1;
pre[n + 1] = n;
sort(a + 1, a + n + 1, cmp);
for (ll i = 1; i <= n; i++)
{
ll l1, l2, r1, r2;
l1 = pre[a[i].id];
if (l1) l2 = pre[l1];
else l2 = -1;
r1 = nxt[a[i].id];
if (r1 != n + 1) r2 = nxt[r1];
else r2 = -1;
if (!(l2 == -1))
ans += (l1 - l2) * (r1 - a[i].id) * a[i].x;
if (!(r2 == -1))
ans += (r2 - r1) * (a[i].id - l1) * a[i].x;
del(a[i].id);
}
cout << ans << "\n";
return 0;
}
|
附：题面翻译
题面描述
给出一个 的排列（即 每个数只出现一次）。
给出一对 ，设 是 中的次大值（第二大值）。
求 。
注：即求所有 区间的次大值之和。
输入格式
第一行一个整数 ，表示之后给出的排列长度为 。
第二行一个长度为 的排列 。
输出格式
输出一个整数，表示
说明/提示
样例 1 解释
，次大值和为 。
数据约束
对于 的数据，保证：
署名：George222
